package com.zlk.algorithm.algorithm.dynamicPlan.longestIncreasingSubsequence;

// 使数组K递增的最少操作次数
// 给你一个下标从0开始包含n个正整数的数组arr，和一个正整数k
// 如果对于每个满足 k <= i <= n-1 的下标 i
// 都有 arr[i-k] <= arr[i] ，那么称 arr 是K递增的
// 每一次操作中，你可以选择一个下标i并将arr[i]改成任意正整数
// 请你返回对于给定的 k ，使数组变成K递增的最少操作次数
// 测试链接 : https://leetcode.cn/problems/minimum-operations-to-make-the-array-k-increasing/
public class Code03_MinimumOperationsToMakeArraykIncreasing {

    //求每个间隔k 组合的数组的最大不降序子序列
    public int kIncreasing(int[] arr, int k) {
        int[] tempArr;
        int ans = 0;
        for (int i = 0; i < k; i++) {
            tempArr = new int[arr.length];
            int size = 0;
            for (int j = i; j <arr.length ; j = j+k) {
                tempArr[size++] = arr[j];
            }
            ans += size-lengthOfNoDecreasing(tempArr,size);
        }
        return ans;
    }

    private int lengthOfNoDecreasing(int[] arr, int size){
        int len = arr.length;
        int[] ends = new int[len];
        int activeLen = 0;
        for (int i = 0; i < size; i++) {
            int index = findLeft(ends,activeLen,arr[i]);
            if(index==-1){
                ends[activeLen++]=arr[i];
            }else{
                ends[index]=arr[i];
            }
        }
        return activeLen;
    }

    private int findLeft(int[] ends, int activeLen, int num){
        int l = 0;
        int r = activeLen-1;
        int mid = 0;
        int ans = -1;
        while (l<=r){
            mid = (l+r)/2;
            if(ends[mid]>num){
                ans = mid;
                r = mid-1;
            }else{
                l = mid+1;
            }
        }
        return ans;
    }

}
